翻訳と辞書 Words near each other ・ Kleisoreia ・ Kleisoura ・ Kleisoura (Byzantine district) ・ Kleisoura, Kastoria ・ Kleisoura, Larissa ・ Kleist ・ Kleist Museum ・ Kleist Prize ・ Kleist Sykes ・ Kleist Theater ・ Kleista Ta Stomata ・ Kleisti ・ Kleistos ・ Kleistpark (Berlin U-Bahn) ・ Kleitias ・ Kleitman–Wang algorithms ・ Kleitomachos ・ Kleitomachos (athlete) ・ Kleiton & Kledir ・ Kleiton Domingues ・ Kleitor ・ Kleitor (Village) ・ Kleitoria ・ Kleitos, Kozani ・ Kleiv Fiskvik ・ Kleive ・ Kleive Church ・ Kleive, Møre og Romsdal ・ Kleiwegkwartier ・ Kleiza Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Kleitman–Wang algorithms ： ウィキペディア英語版 Kleitman–Wang algorithms The Kleitman–Wang algorithms are two different algorithms in graph theory solving the digraph realization problem, i.e. the question if there exists for a finite list of nonnegative integer pairs a simple directed graph such that its degree sequence is exactly this list. For a positive answer the list of integer pairs is called ''digraphic''. Both algorithms construct a special solution if one exists or prove that one cannot find a positive answer. These constructions are based on recursive algorithms. Kleitman and Wang gave these algorithms in 1973. ==Kleitman–Wang algorithm (arbitrary choice of pairs)== The algorithm is based on the following theorem. Let $S=((a\_1,b\_1),\backslash dots,(a\_n,b\_n))$ be a finite list of nonnegative integers that is in nonincreasing lexicographical order and let $(a\_i,b\_i)$ be a pair of nonnegative integers with $b\_i\; >0$. List $S$ is digraphic if and only if the finite list $S\text{'}=((a\_1-1,b\_1),\backslash dots,(a\_-1,b\_),(a\_,0),(a\_-1,b\_),(a\_,b\_),\backslash dots,(a\_n,b\_n))$ has nonnegative integer pairs and is digraphic. Note that the pair $(a\_i,b\_i)$ is arbitrarily with the exception of pairs $(a\_j,0)$. If the given list $S$ digraphic then the theorem will be applied at most $n$ times setting in each further step $S:=S\text{'}$. This process ends when the whole list $S\text{'}$ consists of $(0,0)$ pairs. In each step of the algorithm one constructs the arcs of a digraph with vertices $v\_1,\backslash dots,v\_n$, i.e. if it is possible to reduce the list $S$ to $S\text{'}$, then we add arcs $(v\_i,v\_1),(v\_i,v\_2),\backslash dots,(v\_,v\_),(v\_i,v\_)$. When the list $S$ cannot be reduced to a list $S\text{'}$ of nonnegative integer pairs in any step of this approach, the theorem proves that the list $S$ from the beginning is not digraphic. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kleitman–Wang algorithms」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.